This invention relates generally to a method and apparatus for transmitting of data on an heterogeneous communications network, which has two types of switching nodes: (i) asynchronous and (ii) synchronous with common time reference. More specifically, this invention provides timely forwarding and delivery of data over the network and to their destination nodes. Consequently, the end-to-end performance parameters, such as, loss, delay and jitter, have either deterministic or probabilistic guarantees.
The proliferation of high-speed communications links, fast processors, and affordable, multimedia-ready personal computers brings about the need for wide area networks that can carry real time data, like telephony and video. However, the end-to-end transport requirements of real-time multimedia applications present a major challenge that cannot be solved satisfactorily by current networking technologies. Such applications as video teleconferencing, and audio and video multicasting generate data at a wide range of bit rates and require predictable, stable performance and strict limits on loss rates, average delay, and delay variations (xe2x80x9cjitterxe2x80x9d). These characteristics and performance requirements are incompatible with the services that current circuit and packet switching networks can offer.
Circuit-switching networks, which are still the main carrier for real-time traffic, are designed for telephony service and cannot be easily enhanced to support multiple services or carry multimedia traffic. Its synchronous byte switching enables circuit-switching networks to transport data streams at constant rates with little delay or jitter. However, since circuit-switching networks allocate resources exclusively for individual connections, they suffer from low utilization under bursty traffic. Moreover, it is difficult to dynamically allocate circuits of widely different capacities, which makes it a challenge to support multimedia traffic. Finally, the synchronous byte switching of SONET, which embodies the Synchronous Digital Hierarchy (SDH), requires increasingly more precise clock synchronization as the lines speed increases [Ballart et al., xe2x80x9cSONET: Now It""s The Standard Optical Networkxe2x80x9d, IEEE Communications Magazine, Vol. 29 No. 3, March 1989, pages 8-15] [M. Schwartz, xe2x80x9cTelecommunication Networks: Protocols, Modeling, and Analysisxe2x80x9d, Addison Wesley, Reading Mass., 1987].
Packet switching networks like IP (Internet Protocol)-based Internet and Intranets [see, for example, A.Tannebaum, xe2x80x9cComputer Networksxe2x80x9d (3rd Ed) Prentice Hall, 1996] and ATM (Asynchronous Transfer Mode) [see, for example, Handel et al., xe2x80x9cATM Networks: Concepts, Protocols, and Applicationsxe2x80x9d, (2nd Ed.) Addison-Wesley, 1994] handle bursty data more efficiently than circuit switching, due to their statistical multiplexing of the packet streams. However, current packet switches and routers operate asynchronously and provide best effort service only, in which end-to-end delay and jitter are neither guaranteed nor bounded. Furthermore, statistical variations of traffic intensity often lead to congestion that results in excessive delays and loss of packets, thereby significantly reducing the fidelity of real-time streams at their points of reception. In fact, under best effort service, the performance characteristics of a given connection are not even predictable at the time of connection establishment
Efforts to define advanced services for both IP and ATM have been conducted in two levels: (1) definition of service, and (2) specification of methods for providing different services to different packet streams. The former defines interfaces, data formats, and performance objectives. The latter specifies procedures for processing packets by hosts and switches/routers. The types of services that defined for ATM include constant bit rate (CBR), variable bit rate (VBR) and available bit rate (ABR). For IP, the defined services include guaranteed performance (bit rate, delay), controlled flow, and best effort [J.Wroclawski, xe2x80x9cSpecification of the Controlled-Load Network Element Servicexe2x80x9d, IETF RFC 2211, September 1997] [Shenker et. al., xe2x80x9cSpecification of Guaranteed Quality of Servicexe2x80x9d, IETF RFC 2212. September 1997]. Signaling protocols, e.g., RSVP and UNI3.1, which carry control information to facilitate the establishment of the desired services, are specified for IP and ATM, respectively [R. Braden, xe2x80x9cResource ReSerVation Protocol (RSVP)xe2x80x94Version 1 Functional Specification, IETF Request for Comment RFC2205xe2x80x9d, September 1997] [Handel et al., xe2x80x9cATM Networks: Concepts, Protocols, and Applicationsxe2x80x9d, (2nd Ed.) Addison-Wesley, 1994]. These protocols address the transport of data to one destination known as unicast or multiple destinations multicast [S. Deering, xe2x80x9cMulticast Routing In Datagram Internetxe2x80x9d, Ph.D. Thesis, Stanford University, December 1991]. In addition, SIP, a higher level protocol for facilitating the establishment of sessions that use the underlying services, is currently under definition under IETF auspices [Handley et al., xe2x80x9cSIP-Session Initiation Protocolxe2x80x9d, November 1997].
The methods for providing different services under packet switching fall under the general title of Quality of Service (QoS). Prior art in QoS can be divided into two parts: (1) traffic shaping with local timing without deadline scheduling, for example [M. G. H. Katevenis, xe2x80x9cFast Switching And Fair Control Of Congested Flow In Broadband Networksxe2x80x9d, IEEE Journal on Selected Areas in Communications, SAC-5(8):1315-1326, October 1987; Demers et al., xe2x80x9cAnalysis and Simulation Of A Fair Queuing Algorithmxe2x80x9d, ACM Computer Communication Review (SIGCOMM""89), pages 3-12, 1989; S. J. Golestani, xe2x80x9cCongestion-Free Communication In High-Speed Packet Networksxe2x80x9d, IEEE Transcripts on Communications, COM-39(12):1802-1812, December 1991; Parekh et al., xe2x80x9cA Generalized Processor Sharing Approach To Flow Controlxe2x80x94The Multiple Node Casexe2x80x9d, IEEE/ACM T. on Networking, 2(2):137-150, 1994], and (2) traffic shaping with deadline scheduling, for example [Ferrari et al., xe2x80x9cA Scheme For Real-Time Channel Establishment In Wide-Area Networksxe2x80x9d, IEEE Journal on Selected Areas in Communication, SAC-8(4):368-379, April 1990; Kandlur et al., xe2x80x9cReal Time Communication In Multi-Hop Networksxe2x80x9d, IEEE Trans. on Parallel and Distributed Systems, Vol. 5, No. 10, pp. 1044-1056, 1994]. Both of these approaches rely on manipulation of local queues by each router with little coordination with other routers. The Weighted Fair Queuing (WFQ), which typifies these approaches, is based on cyclical servicing of the output port queues where the service level of a specific class of packets is determined by the amount of time its queue is served each cycle [Demers et al., xe2x80x9cAnalysis and Simulation Of A Fair Queuing Algorithmxe2x80x9d, ACM Computer Communication Review (SIGCOMM""89), pages 3-12, 1989]. These approaches have inherent limitations when used to transport real-time streams. When traffic shaping without deadline scheduling is configured to operate at high utilization with no loss, the delay and jitter are inversely proportional to the connection bandwidth, which means that low rate connections may experience large delay and jitter inside the network. In traffic shaping with deadline scheduling the delay and jitter are controlled at the expense of possible congestion and loss.
The recognition that the processing of packets by switches and routers constitutes a performance bottleneck resulted in the development of methods for enhancing performance by simplifying the processing of packets. Multiprotocol Label Switching (MPLS) converts the destination address in the packet header into a short tag, which defines the routing of the packet inside the network [Callon et al., xe2x80x9cA Proposed Architecture For MPLSxe2x80x9d, August 1997].
The real-time transport protocol (RTP) [M. Schultzrinne et. al, RTP: A Transport Protocol for Real-Time Applications, IETF Request for Comment RFC1889, January 1996] is a method for encapsulating time-sensitive data packets and attaching to the data time related information like time stamps and packet sequence number. RTP is currently the accepted method for transporting real time streams over IP internetworks and packet audio/video telephony based on ITU-T H.323.
Synchronous methods are found mostly in circuit switching, as compared to packet switching that uses mostly asynchronous methods. However, some packet switching synchronous methods have been proposed. IsoEthernet or IEEE 802.9a [IEEE 802.9a Editor. Integrated service (is): IEEE 802.9a xe2x80x9cIsochronous Services With CSMA/CD MAC Servicexe2x80x9d, IEEE Draft, March 1995] combines CSMA/CD (EEE 802.3), which is an asynchronous packet switching, with N-ISDN and H.320, which is circuit switching, over existing Ethernet infrastructure (10Base-T). This is a hybrid solution with two distinct switching methods: N-ISDN circuit switching and Ethernet packet switching. The two methods are separated in the time domain by time division multiplexing (TDM). The IsoEthernet TDM uses fixed allocation of bandwidth for the two methodsxe2x80x94regardless of their utilization levels. This approach to resource partitioning results in undesirable side effect like under-utilization of the circuit switching part while the asynchronous packet switching is over loaded but cannot use the idle resources in the circuit switching part.
One approach to an optical network that uses synchronization was introduced in the synchronous optical hypergraph [Y. Off, xe2x80x9cThe Topology, Algorithms And Analysis Of A Synchronous Optical Hypergraph Architecturexe2x80x9d, Ph.D. Dissertation, Electrical Engineering Department, University of Illinois at Urbana, Report No. UIUCDCS-R-87-1343, May 1987], which also relates to how to integrate packet telephony using synchronization [Y. Ofek, xe2x80x9cIntegration Of Voice Communication On A Synchronous Optical Hypergraphxe2x80x9d, INFOCOM""88, 1988]. In the synchronous optical hypergraph, the forwarding is performed over hyper-edges, which are passive optical stars. In [Li et al., xe2x80x9cPseudo-Isochronous Cell Switching In ATM Networksxe2x80x9d, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., xe2x80x9cTime-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworkingxe2x80x9d, IEEE INFOCOM""96, 1996] the synchronous optical hypergraph idea was applied to networks with an arbitrary topology and with point-to-point links. The two papers [Li et al., xe2x80x9cPseudo-Isochronous Cell Switching In ATM Networksxe2x80x9d, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., xe2x80x9cTime-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworkingxe2x80x9d, IEEE INFOCOM""96, 1996] provide an abstract (high level) description of what is called xe2x80x9cRISC-like forwardingxe2x80x9d, in which a packet is forwarded, with little if any details, one hop every time frame in a manner similar to the execution of instructions in a Reduced Instruction Set Computer (RISC) machine [Patterson et al., xe2x80x9cComputer Architecture: A Quantitative Approachxe2x80x9d, Morgan Kaufman Publishers, San Francisco, 1990]. In U.S. Pat. No. 5,455,701, Eng et al. discloses an apparatus for controlling a high-speed optical switching system with pipeline controller for switch control. In U.S. Pat. No. 5,418,779 Yemini et al disclose a switched network architecture with common time reference. The time reference is used in order to determine the time in which multiplicity of nodes can transmit simultaneously over one predefined routing tree to one destination. At every time instance the multiplicity of nodes are transmitting to different single destination node.
This invention describes a method for exchanging timing messages and data packets between synchronous switches with a common time reference, and between end-stations/gateways and other synchronous switchesxe2x80x94over an asynchronous network, i.e., a network with asynchronous switches. The method entails transmission of messages conveying the common time reference to end-station/gateways that have no direct access to the common time reference, and data packets that are sent responsive to the timing information and predetermined scheduled time intervals.
The invention describes a method for transmitting and forwarding packets over a packet switching network where the delay between two synchronous switches changes in an unpredictable manner, but with a known delay bound, since there are one or more asynchronous switches in between. The synchronous switches of the network maintain a common time reference, which is obtained either from an external source (such as GPS-Global Positioning System) or is generated and distributed internally. The time intervals are arranged with simple periodicity and complex periodicity (like seconds and minutes of a clock).
The common time reference is used to determine in advance the periodic time intervals a packet will be forwarded by each synchronous switch on its route from source to destination. The time interval duration can be longer than the time duration required for transmitting a packet, in which case the exact position of a packet in the time interval is not predetermined. A packet that arrives to an input port is switched to an output port based on specific routing information in the packet""s header (e.g., IPv4 destination address in the Internet, VCI/VPI labels in ATM) and the time interval of its arrival.
Packets that are forwarded inside the network over the same route and in the same time intervals constitute a virtual pipe and share the same pipe-ID. Pipe-ID can be either explicit, such as a tag or a label that is generated inside the network, or implicit such as a group of IP addresses. Virtual pipe provides deterministic quality of service guarantees. The time interval in which a switch forwards a specific packet is determined by the packet""s pipe-ID, the time it reaches the switch, and the current value of the common time reference.
The invention provides methods for maintaining timely forwarding within predefined time interval over three network configurations: (i) end-station to synchronous switch over asynchronous (LAN) switches, (ii) end-station to gateway over asynchronous (LAN) switches and then to synchronous switch, (iii) synchronous switch to synchronous switch over asynchronous switches.
The method disclosed in this invention combines the advantages of both circuit and packet switching. It provides for allocation for the exclusive use of predefined connections and for those connections it guarantees loss free transport with low delay and jitter. When predefined connections do not use their allocated resources, other non-reserved data packets can use them without affecting the performance of the predefined connections. On the Internet the non-reserved data packet traffic is called xe2x80x9cbest effortxe2x80x9d traffic. In accordance with the present invention, the bandwidth allocated to a connection and the delay and jitter inside the network are independent MPLS [R. Callon et al., A proposed architecture for MPLS less than draft-ietf-mpls-arch-00.txt greater than INTERNET DRAFT, August 1997] can be used by the present invention to identify virtual pipes. The packet time-stamp that is carried in the RTP header can be used in accordance with the present invention to facilitate time-based transport.
Under the aforementioned prior art methods for providing packet switching services, all switches and routers operate asynchronously. The present invention provides real-time services by synchronous methods that utilize a time reference that is common to the synchronous switches and end stations comprising a local/wide area network. The common time reference can be realized by using UTC (Coordinated Universal Time), which is globally available via, for example, GPS (Global Positioning System-see, for example: www.utexas.edu/depts/grg/gcraft/notes/gps/gps.html). By international agreement, UTC is the same all over the world. UTC is the scientific name for what is commonly called GMT (Greenwich Mean Time), the time at the 0 (root) line of longitude at Greenwich, England. In 1967, an international agreement established the length of a second as the duration of 9,192,631,770 oscillations of the cesium atom The adoption of the atomic second led to the coordination of clocks around the world and the establishment of UTC in 1972. The Time and Frequency Division of the National Institute of Standards and Technologies (NIST) (see www.boulder.nis.gov/timefreq) is responsible for coordinating with the International Bureau of Weights and Measures (BIPM) in Paris in maintaining UTC.
UTC timing is readily available to individual PCs through GPS cards. For example, TrueTime, Inc.""s (Santa Rosa, Calif.) PCI-SG provides precise time, with zero latency, to computers that have PCI extension slots. Another way by which UTC can be provided over a network is by using the Network Time Protocol (NTP) [D. Mills, xe2x80x9cNetwork Time Protocorxe2x80x9d (version 3) IETF RFC 1305]. However, the clock accuracy of NTP is not adequate for interswitch coordination, on which this invention is based.
In accordance with the present invention, the use of reserved resources is allowed by all packet traffic whenever the reserved resources are not in use.
Although the present invention relies on time to control the flow of packets inside the network in a similar fashion as in circuit switching, there are major differences between the two approaches. In circuit switching, for each data unit (e.g., a byte) at the time it has been transmitted from its source, it is possible to predict deterministically the future times it will be transmitted from any switch along its route [Ballart et al., xe2x80x9cSONET: Now It""s The Standard Optical Networkxe2x80x9d, IEEE Communications Magazine, Vol. 29 No. 3, March 1989, pages 8-15]. The time resolution of this advanced knowledge is much shorter than the data unit transmission time. On the other hand, in accordance with the present invention, for each data unit (e.g., a cell) at the time it has been transmitted from its source, it is possible to know the future time frames that this data unit will be forwarded along its route. However, the time frame, which constitutes the accuracy of this advance timing knowledge, is much larger than one data unit transmission time. For example, the transmission time of an ATM cell (53 bytes) over a gigabit per second link is 424 nanoseconds,. which is 294 times. smaller than a typical time frame of 125 microsecondsxe2x80x94used in one embodiment of the present invention. There are several consequences that further distinguish the present invention from circuit switching:
In accordance with the present invention, the synchronization requirements are independent of the physical link transmission speed, while in circuit switching the synchronization becomes more and more difficult as the link speed increases.
In accordance with the present invention, timing information is not used for routing, and therefore, in the Internet, for example, the routing is done using IP addresses or a tag/label.
In accordance with the present invention, the Internet xe2x80x9cbest effortxe2x80x9d packet forwarding strategy can be integrated into the system.
These and other aspects and attributes of the present invention will be discussed with reference to the following drawings and accompanying specification.